package com.hanlin.day01;

/**
 * 描述：算法入门级别：冒泡排序、选择排序、插入排序
 * 总结：
 * 冒泡排序：就是两两比对，然后小的调换位置。如果有4个数，需要第一轮比较次数为3 ，第二轮比较次数为2，第三轮比较次数为1
 *         代码逻辑：第一层循环控制循环次数，i从数组长度减一开始，i--，一直到i>0，然后第二层循环就是j=0 ,j小于i,j-- 一直到j>0，然后就是比较
 *         j>j+1的话，就调换位置。这里j为什么是从0开始，是因为冒泡排序，每一层排序玩，最大的事，必然会在最后一个下标上面，其实就是每一层循环就是把最大的
 *         数给调出来，然后挪到后面。
 *
 * 选择排序：在所有的数据中跳出最小的数，然后放在最前面的位置：如下标为0的是最小，下标为1的是第二小。
 *         代码逻辑：第一层循环控制循环次数，i从0开始，到数组的长度为止，第二个循环j从i的值，开始，到数组的长度减一为止，然后在这一轮里面挑出一个最小的数，和i调换位置
 *
 * 插入排序：每次循环 就是比较上一个下标，如果小于，就调换位置，直达遇见比自己大的，才停止。如第一轮循环比较从下标1开始，第二轮循环是下标2开始，以此类推
 *         代码逻辑：第一层循环控制比较次数，i从1开始，到数组的长度为止，第二层循环j从i的值开始，到0为止，就是j--的操作。然后判断当前数，和上一个下标的数据的大小
 *         如果j<j-1的话，需要调换位置，如果j>j-1的话，说明遇见比自己大的，直接break;
 *
 * @author:hl.yuan
 * @date:2021-05-25
 */
public class DataSort {

    /**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        /**
         * 冒泡排序 ： 如果是  1 5 2 4  这个四个数
         * 第一轮 1和5比较：位置不变  5和2比较：2和5调换位置 1 2 5 4；  5和4比较：5和4调换位置 1245
         * 第二轮 1和2比较 ；2和4比较
         * 第三轮 1和2比较
         *
         * 所以第一个循环控制轮数 N-1 次循环
         * 第二个循环控制比较次数：和轮数相同
         * 然后就是在比较的时候，比较下标N和N+1，如果N大于N+1的话，就调换位置
         *
         */
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    exchangeData(arr, j, j + 1);
                }
            }
        }
    }

    /**
     * 选择排序
     *
     * @param arr 数组
     */
    public static void selectSort(int[] arr) {
        /*
         * 选择排序： 每次循环都把最小的给挑出来，然后放在最前面
         * 案例 2 1 4 3 ：第一次比较，从下标0开始，会查出1是最小的，然后把1和2进行对换位置： 1 2 4 3
         *               第二次比较：从下标1开始，会查出2是最小的，发现2就是最小的，就交换  1 2 4 3
         *               第三次比较：从下标2开始，会查出3是最小的，然后把三和四进行调换位置  1 2 3 4
         *
         */

        // 控制外层比较次数
        for (int i = 0; i < arr.length; i++) {
            // 记录最小的值
            int minValueIndex = i;
            // 每一层比较的次数
            for (int j = i; j < arr.length; j++) {
                // 我们需要拿着最小的数，和当前循环的数进行比较
                // 三目表达式解析：如果当前数大于记录的最小数，那么说明最小数还是minValueIndex否则就是当前数
                minValueIndex = arr[j] > arr[minValueIndex] ? minValueIndex : j;
            }
            // 拿到最小数后，我们需要把i位置的值，和最小数的值，调换位置
            exchangeData(arr, i, minValueIndex);
        }


    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        /**
         * 插入排序 案例： 2 1 4 3 7 6
         * 第一层比较： 1和2比较 然后1比2小，调换位置  1 2 4 3 7 6
         * 第二层比较： 4和2比较，4比2大，位置不动，故后面就不用比了
         * 第三层比较： 3和4比较，3比4小，调换位置，1 2 3 4 7 6  然后3和2比较，3比2大 ，位置就不变
         * 第四层比较： 7和4比较，7比四大，位置不动
         * 第五层比较： 6和7比较，6比7小，调换位置 1 2 3 4 6 7 然后6和4比较 6比4大，位置不变
         */
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j-1]) {
                    exchangeData(arr, j, j-1);
                }else {
                    break;
                }
            }
        }

    }


    /**
     * 交换位置
     *
     * @param arr 数组
     * @param i   要交换的值
     * @param j   要交换的新值
     */
    public static void exchangeData(int[] arr, int i, int j) {
        int item = arr[i];
        arr[i] = arr[j];
        arr[j] = item;
    }

    /**
     * 打印arr数组
     *
     * @param arr
     */
    public static void printlnArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int param[] = {66, 76, 43, 99, 52, 43, 68, 25};

        printlnArray(param);
        selectSort(param);
        printlnArray(param);
    }

}
